const validatePwd = (input: string): string => {
  if (input.length < 8) return "NG";
  let type = [false, false, false, false];

  for (const element of input) {
    if (element >= "A" && element <= "Z") {
      type[0] = true;
    } else if (element >= "a" && element <= "z") {
      type[1] = true;
    } else if (element >= "0" && element <= "9") {
      type[2] = true;
    } else {
      if (element === " " || element === "/n") return "NG";
      type[3] = true;
    }
  }
  let amount = 0;
  type.forEach((t) => {
    if (t) amount += 1;
  });
  console.log(type);

  if (amount < 3) return "NG";

  for (let i = 3; i < input.length - 1; i++) {
    for (let j = 0; j < input.length - i; j++) {
      if (input.slice(j + i, input.length).includes(input.slice(j, j + i))) {
        return "NG";
      }
    }
  }
  return "OK";
};

function scheduleCourse(courses: number[][]): number {
  console.log(courses);
  // d > l 的一定不会修完
  let filterCourses = courses.filter((c) => c[0] < c[1]);
  let deadline = 0;
  let coursesToDo = [];
  if (filterCourses.length) {
    filterCourses.sort((a, b) => a[1] - b[1]);
    console.log(filterCourses);
    filterCourses.forEach((c) => {
      coursesToDo.push(c);
    });
  } else {
    return 0;
  }
  return 0;
}

const findMiddleNum = (nums: number[]) => {
  let dic: { [key: string]: number } = {};
  let max = 0;
  nums.forEach((n) => {
    if (dic.hasOwnProperty(n)) {
      dic[n] += 1;
    } else {
      dic[n] = 1;
    }
    max = Math.max(max, dic[n]);
  });

  console.log(dic);

  const tmp: number[] = [];
  Object.keys(dic).forEach((k) => {
    if (dic[k] === max) {
      tmp.push(Number(k));
    }
  });
  tmp.sort((a, b) => a - b);
  console.log(tmp);

  if (tmp.length % 2 === 0) {
    return (tmp[tmp.length / 2 - 1] + tmp[tmp.length / 2]) / 2;
  } else {
    return tmp[Math.floor(tmp.length / 2)];
  }
};

const basketballMatch = (players: number[]) => {
  let total = 0;
  let difference = Infinity;
  players.forEach((p) => (total += p));
  const dfs = (pos: number, tmp: number[]) => {
    tmp.push(players[pos]);

    if (pos >= players.length) return;
    if (tmp.length === 5) {
      let aTeam = 0;
      tmp.forEach((t) => (aTeam += t));
      difference = Math.min(difference, Math.abs(total - 2 * aTeam));
      return;
    }

    for (let i = pos + 1; i < players.length; i++) {
      dfs(i, tmp);
      tmp.pop();
    }
  };
  for (let i = 0; i < players.length - 5; i++) {
    dfs(i, []);
  }
  console.log(difference);
};

const findFriends = (friends: number[]) => {
  let res = Array(friends.length).fill(0);
  for (let i = friends.length - 1; i >= 0; i--) {
    for (let j = i - 1; j >= 0; j--) {
      if (friends[i] > friends[j]) {
        res[j] = i;
      }
    }
  }
  console.log(res);
  return res;
};

const takeTaxi = (num: number) => {
  // 检查num中每一位存在多少个4
  let total = 0;
  let cmp = 1;
  while (num) {
    total += (num % 10 > 4 ? (num % 10) - 1 : num % 10) * cmp;
    num = Math.floor(num / 10);
    cmp *= 9;
  }
  console.log(total);
  return total;
};

const eatPeaches = (piles: number[], h: number) => {
  console.log(piles, h);
  let left = 1;
  let right = Math.max(...piles);
  let middle;

  const calcSum = (speed: any) => {
    let total = 0;
    piles.forEach((element) => {
      total += Math.ceil(element / speed);
    });
    return total;
  };

  while (left < right) {
    console.log(left, right);

    middle = Math.floor(left + (right - left) / 2);
    if (calcSum(middle) > h) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;
};

const generateSpecificString = (str: string, len: number) => {
  let ans = new Set<string>();
  const visited = Array(str.length).fill(false);
  const traceback = (pos: number, tmp: string) => {
    if (tmp.length === len) {
      ans.add(tmp);
      return;
    }
    for (let i = 0; i < str.length; i++) {
      if (visited[i] || (tmp?.length > 0 && str[i] === tmp[tmp.length - 1])) {
        continue;
      }
      visited[i] = true;
      traceback(i, tmp + str[i]);
      visited[i] = false;
    }
  };

  for (let i = 0; i < str.length; i++) {
    visited[i] = true;
    traceback(i, str[i]);
    visited[i] = false;
  }
  return ans.size;
};

const vowelString = (clean: number, str: string) => {
  const VOWELS = ["a", "e", "i", "o", "u"];

  const isCleanVoWelString = (str: string) => {
    if (!str.length) return;
    if (str[0] !== str[str.length - 1]) return false;
    let dirty = 0;
    for (let i = 0; i < str.length - 1; i++) {
      if (!VOWELS.includes(str[i])) {
        dirty += 1;
      }
      if (dirty > clean) return false;
    }
    if (dirty < clean) return false;
    return true;
  };

  const ans: string[] = [];

  const traceback = (pos: number, currentStr: string) => {
    console.log(pos, currentStr);

    for (let i = pos; i < str.length; i++) {
      console.log(currentStr);

      if (isCleanVoWelString(currentStr)) {
        ans.push(currentStr);
      }
      traceback(i + 1, currentStr + str[i]);
    }
  };

  traceback(0, "");

  console.log(ans);
};

const constantNaturalNumber = (num: number) => {
  let numList = [];
  for (let i = num; i >= 0; i--) {
    let cmp = i;
    let tmp = [];
    let total = 0;
    while (cmp > 0 && total < num) {
      tmp.push(cmp);
      total += cmp;
      cmp--;
    }
    if (total === num) {
      numList.push(tmp);
    }
  }
  console.log(numList);
};

const findSeats = (seats: string) => {
  let seated = seats.split("");

  let amount = 0;
  for (let i = 0; i < seated.length; i++) {
    if (seated[i] === "1") {
      i += 1;
      continue;
    }

    if (seated[i + 1] !== "1" && seated[i - 1] !== "1") {
      seated[i] = "1";
      amount += 1;
      i += 1;
    }
  }
  console.log(seated, amount);
  return amount;
};

const sushi = (sushis: number[]) => {
  let result = [];

  for (let i = 0; i < sushis.length; i++) {
    let flag = false;
    let tmp = sushis[i];
    for (let j = i; j < sushis.length; j++) {
      if (sushis[j] < sushis[i]) {
        tmp += sushis[j];
        flag = true;
        break;
      }
    }
    if (!flag) {
      for (let j = 0; j < i + 1; j++) {
        if (sushis[j] < sushis[i]) {
          tmp += sushis[j];
          break;
        }
      }
    }
    result.push(tmp);
  }

  console.log(result);
};

const findCheaters = (examinee: [number, number][]) => {
  const sortedExaminee = examinee.sort((a, b) => a[1] - b[1]);
  const difference = [];
  let min_difference = Infinity;
  for (let i = 0; i < sortedExaminee.length - 1; i++) {
    difference.push(sortedExaminee[i + 1][1] - sortedExaminee[i][1]);
    min_difference = Math.min(
      min_difference,
      sortedExaminee[i + 1][1] - sortedExaminee[i][1]
    );
  }
  // difference.push(
  //   sortedExaminee[sortedExaminee.length - 1][1] - sortedExaminee[0][1]
  // );
  // min_difference = Math.min(
  //   min_difference,
  //   sortedExaminee[sortedExaminee.length - 1][1] - sortedExaminee[0][1]
  // );
  console.log(sortedExaminee, difference, min_difference);

  let res: [number, number][] = [];

  difference.forEach((ele, index) => {
    if (ele === min_difference) {
      // if (index === difference.length - 1) {
      // res.push([sortedExaminee[index][0], sortedExaminee[0][0]]);
      // } else {
      res.push([sortedExaminee[index][0], sortedExaminee[index + 1][0]]);
      // }
    }
  });

  console.log(res);

  res.map((r) => {
    return r.sort();
  });

  res.sort();
  return res;
};

const findLongestO = (str: string) => {
  let indexes: number[] = [];
  str.split("").forEach((e, i) => {
    if (e === "o") indexes.push(i);
  });

  console.log(indexes);

  let min_distance = Infinity;
  for (let i = 0; i < indexes.length - 1; i++) {
    if (indexes)
      min_distance = Math.min(indexes[i + 1] - indexes[i], min_distance);
  }
  // min_distance = Math.min((indexes[indexes.length - 1] = indexes[0]), min_distance);

  console.log(
    Math.max(
      str.length - min_distance + 1,
      indexes[indexes.length - 1] - indexes[0]
    )
  );
  return Math.max(
    str.length - min_distance + 1,
    indexes[indexes.length - 1] - indexes[0]
  );
};

const cacheVisit = (visits: number[], threshold: number) => {
  let dic: { [key: string]: number } = {};
  visits.forEach((v) => {
    if (dic.hasOwnProperty(v)) {
      dic[v] += 1;
    } else {
      dic[v] = 1;
    }
  });
  console.log(dic);
  let res: number[] = [];
  Object.keys(dic).forEach((k) => {
    if (dic[k] >= threshold) res.push(Number(k));
  });
  console.log(res);

  console.log(res.length);
  if (res?.length) console.log(res.join(" "));
};

const balancedString = (str: string) => {
  let a = 0;
  let b = 0;
  let res = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === "X") {
      a += 1;
    }
    if (str[i] === "Y") {
      b += 1;
    }
    if (a === b) {
      a = 0;
      b = 0;
      res += 1;
    }
  }
  console.log(res);
};

const lowestUnitSort = (nums: number[]) => {
  let res: number[] = [];
  for (let i = 0; i < 10; i++) {
    nums.forEach((ele) => {
      if (Math.abs(ele) % 10 === i) {
        res.push(ele);
      }
    });
  }
  console.log(res);
  return res;
};

const deDuplicationAndSort = (nums: number[]) => {
  let myMap = new Map();
  let res: number[] = [];
  nums.forEach((ele) => {
    if (myMap.has(ele)) {
      myMap.set(ele, myMap.get(ele) + 1);
    } else {
      myMap.set(ele, 1);
    }
  });
  let tmp = Array.from(myMap);

  tmp.sort((a, b) => b[1] - a[1]);

  tmp.forEach((t) => res.push(t[0]));

  return res.join(",");
};

const sortedByHeightAndWeight = (heights: number[], weights: number[]) => {
  let myMap = new Map();
  let len = heights.length;
  for (let i = 0; i < len; i++) {
    myMap.set(i + 1, [heights[i], weights[i]]);
  }

  console.log(myMap);
  let tmp = Array.from(myMap);
  // 根据身高排序
  tmp.sort((a, b) => a[1][0] - b[1][0]);
  tmp.sort((a, b) => {
    if (a[1][0] === b[1][0]) return a[1][1] - b[1][1];
    return 0;
  });
  console.log(tmp);
  let res: number[] = [];
  tmp.forEach((t) => res.push(t[0]));
  return res.join(",");
};

const switchString = (str: string) => {
  let minChar = undefined;
  let res = str;
  for (
    let switchChar = 0;
    switchChar < Math.ceil(str.length / 2);
    switchChar++
  ) {
    minChar = undefined;
    for (let i = str.length - 1; i > switchChar; i--) {
      if (str[switchChar] > str[i]) {
        if (minChar) {
          minChar = str[i] > str[minChar] ? i : minChar;
        } else {
          minChar = i;
        }
      }
    }
    console.log(switchChar, minChar);

    if (minChar) {
      res =
        str.slice(0, switchChar) +
        str[minChar] +
        str.slice(switchChar + 1, minChar) +
        str[switchChar] +
        str.slice(minChar + 1, str.length);
      console.log(res);
      break;
    }
  }
  return res;
};

const GPUAssignments = (threshold: number, assignments: number[]) => {
  let remainAssignment = 0;
  let res = 0;

  for (let i = 0; i < assignments.length; i++) {
    res += 1;
    if (assignments[i] < threshold) {
      remainAssignment += 0;
      if (remainAssignment > threshold - assignments[i]) {
        remainAssignment -= threshold - assignments[i];
      } else {
        remainAssignment = 0;
      }
    } else {
      remainAssignment += assignments[i];
      remainAssignment -= threshold;
    }

    console.log(remainAssignment);
  }
  if (remainAssignment) {
    res += Math.ceil(remainAssignment / threshold);
  }

  return res;
};

const wordsAssociation = (sentences: string, prefix: string) => {
  console.log(sentences, prefix);
  let library = new Set(sentences.split(" "));

  let res: string[] = [];

  library.forEach((l) => {
    if (l.indexOf(prefix) === 0) {
      res.push(l);
    }
  });
  console.log(res);
};

const jointPrefixAndSuffix = (prefix: string, suffix: string) => {
  if (prefix[prefix.length - 1] === "/")
    prefix = prefix.slice(0, prefix.length - 1);
  if (suffix[0] === "/") suffix = suffix.slice(1, suffix.length);
  console.log(prefix + "/" + suffix);
  return prefix + "/" + suffix;
};

const parkingLot = (cars: number[]) => {
  let str = "";
  cars.forEach((c) => (str += String(c)));

  let lots = str.split("0");
  console.log(lots);
  let res = 0;
  lots.forEach((lot) => {
    if (lot.length <= 3) {
      res += 1;
    } else {
      let middle = lot.length % 3;
      res += Math.floor(lot.length / 3);
      let small = middle % 2;
      res += Math.floor(middle / 2);
      res += small;
    }
  });
  console.log(res);
  return res;
};

const mostDispatchingTeam = (abilities: number[], threshold: number) => {};

const findConstantArea = (comp: number, nums: number[]) => {
  nums = nums.sort((a, b) => a - b);
  console.log(nums, nums.length);
  let res = 0;

  for (let cmp = nums.length; cmp >= 1; cmp--) {
    let amount = nums.length - cmp + 1;
    console.log(amount, cmp, "amount");
    for (let i = 0; i < nums.length - cmp + 1; i++) {
      let total = nums.slice(i, i + cmp).reduce((p, c) => p + c);
      if (total >= comp) {
        console.log(amount, "add");

        res += amount;
        break;
      }
      amount -= 1;
    }
  }
  console.log(res);
  return res;
};

export {
  validatePwd,
  scheduleCourse,
  findMiddleNum,
  basketballMatch,
  findFriends,
  takeTaxi,
  eatPeaches,
  generateSpecificString,
  vowelString,
  constantNaturalNumber,
  findSeats,
  sushi,
  findCheaters,
  findLongestO,
  cacheVisit,
  balancedString,
  lowestUnitSort,
  deDuplicationAndSort,
  sortedByHeightAndWeight,
  switchString,
  GPUAssignments,
  wordsAssociation,
  jointPrefixAndSuffix,
  parkingLot,
  mostDispatchingTeam,
  findConstantArea,
};
